package leetcode_zh

import "sort"

/**
 * @Description: 剑指 Offer II 041. 滑动窗口的平均值 简单
 * @Keyword: TODO
 * @Author: kami
 * @Date: 2022/6/22 9:59
 **/
type MovingAverage struct {
	index int
	count int
	sum   int
	cache []int
}

/** Initialize your data structure here. */
func ConstructorAverage(size int) MovingAverage {
	return MovingAverage{index: size - 1, cache: make([]int, size)}
}

func (this *MovingAverage) Next(val int) float64 {
	this.sum += val
	this.index = (this.index + 1) % len(this.cache)
	if this.count < len(this.cache) {
		this.count++
		this.cache[this.index] = val
	} else {
		this.sum -= this.cache[this.index]
		this.cache[this.index] = val
	}
	return float64(this.sum) / float64(this.count)
}

/**
 * Your MovingAverage object will be instantiated and called as such:
 * obj := Constructor(size);
 * param_1 := obj.Next(val);
 */
/**
 * @Description: 剑指 Offer 59 - I. 滑动窗口的最大值 困难
 * @Keyword: 滑动窗口
 * @Author: kami
 * @Date: 2022/6/22 10:18
 **/
func maxSlidingWindow59(nums []int, k int) []int {
	var res []int
	var win []int
	for i := 0; i < len(nums); i++ {
		if i >= k && win[0] <= i-k {
			win = win[1:]
		}
		var size = len(win)
		for size > 0 && nums[win[size-1]] <= nums[i] {
			win = win[:size-1]
			size--
		}
		win = append(win, i)

		if i >= k-1 {
			res = append(res, nums[win[0]])
		}
	}
	return res
}

/**
 * @Description: 480. 滑动窗口中位数 中等
 * @Keyword: 二分查找 + 冒泡排序
 * @Author: kami
 * @Date: 2022/6/22 10:29
 **/
func medianSlidingWindow(nums []int, k int) []float64 {
	res := make([]float64, len(nums)-k+1)
	window := make([]int, k)
	//添加初始值
	for i := 0; i < k; i++ {
		window[i] = nums[i]
	}
	// 初始的快排，懒得写直接调用
	sort.Ints(window)
	res[0] = getMid(window)
	// 窗口滑动
	for i := 0; i < len(nums)-k; i++ {
		// 需要删除的数
		index := search480(window, nums[i])
		// 替换为需要插入的数
		window[index] = nums[i+k]
		// 向后冒泡
		for index < len(window)-1 && window[index] > window[index+1] {
			swap(window, index, index+1)
			index++
		}
		// 向前冒泡
		for index > 0 && window[index] < window[index-1] {
			swap(window, index, index-1)
			index--
		}
		res[i+1] = getMid(window)
	}
	return res
}

// swap 交换
func swap(window []int, i, j int) {
	window[i], window[j] = window[j], window[i]
}

// getMid 求数组的中位数
func getMid(window []int) float64 {
	l := len(window)
	if l%2 == 0 {
		// 避免溢出，分开计算
		return float64(window[l/2])/2.0 + float64(window[l/2-1])/2.0
	} else {
		return float64(window[l/2])
	}
}

// search 二分查找
func search480(window []int, target int) int {
	left, right := 0, len(window)
	for left < right {
		mid := left + (right-left)/2
		if window[mid] > target {
			right = mid
		} else if window[mid] < target {
			left = mid + 1
		} else {
			return mid
		}
	}
	return -1
}

func medianSlidingWindowKsort(nums []int, k int) []float64 {
	knums := make([]int, k)
	copy(knums, nums[:k])
	sort.Ints(knums)
	ret := make([]float64, len(nums)-k+1)
	ret[0] = calMid(knums, k)
	for i := k; i < len(nums); i++ {
		delIdx := binarySearch(knums, nums[i-k])

		knums = append(knums[:delIdx], knums[delIdx+1:]...)
		addIdx := binarySearch(knums, nums[i])
		last := append([]int{nums[i]}, knums[addIdx:]...)
		knums = append(knums[:addIdx], last...)
		ret[i-k+1] = calMid(knums, k)
	}
	return ret
}

func binarySearch(nums []int, val int) int {
	low, high := 0, len(nums)-1
	for low <= high {
		mid := low + (high-low)/2
		if nums[mid] == val {
			return mid
		} else if nums[mid] > val {
			high = mid - 1
		} else {
			low = mid + 1
		}
	}
	return low
}

func calMid(nums []int, k int) float64 {
	n1, n2 := 0, 0
	if k%2 == 0 {
		n1, n2 = nums[k/2-1], nums[k/2]
	} else {
		n1, n2 = nums[k/2], nums[k/2]
	}
	return float64(n1+n2) / float64(2)
}
